﻿#include <iostream>
#include <iomanip>
#include "Simplesort.h"

using namespace std;

void Simplesort::PrintResult(int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr)
    {
        return;
    }
    for (int i = 0; i < n; i++)
    {
        cout << setw(4) << Arr[i];
    }
    cout << endl;
}

void Simplesort::BubbleSort(int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr)
    {
        return;
    }
    bool iHasSwap = true;//当前遍历有数据交换发生，若没有，则表示数据已有序，无需再遍历
    for (int i = 0; i < n; i++)
    {
        iHasSwap = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (Arr[j] > Arr[j + 1])//交换位置
            {
                int temp = Arr[j + 1];
                Arr[j + 1] = Arr[j];
                Arr[j] = temp;
                iHasSwap = true;
            }
        }
        if (false == iHasSwap)
        {
            break;
        }
    }
}

void Simplesort::InsertSort(int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr)
    {
        return;
    }
    for (int i = 1; i < n; i++)//数组第一个元素直接放在有序空间，所以从第二个元素开始
    {
        int value = Arr[i];
        int j = i - 1;
        for (; j>=0; j--)
        {
            if (Arr[j] > value)//j开始的元素依次向后移动
            {
                Arr[j + 1] = Arr[j];
            }
            else 
            {
                break; //如果在已排序区间内找到<=插入值的数，则退出，否则循环结束后j+1的位置就不是插入位置了
            }
        }
        Arr[j + 1] = value;//value插在原来j的位置
    }
}

void Simplesort::SelectSort(int* Arr, int n)
{
    if (n <= 1 || Arr == nullptr)
    {
        return;
    }
    int min;
    for (int i = 0; i < n-1; i++)//初始已排序区间为0，最后一个数无需排序，所以i范围0~n-1
    { 
        min = Arr[i]; //选取未排序空间的第一个数作比较
        for (int j = i; j < n; j++)//从i开始到n为未排序空间，遍历所有元素找最小值
        {
            if (Arr[j] < min)
            {
                swap(min, Arr[j]);//最小值更新数据
            }
        }
        Arr[i] = min;//最小值放入已排序区间的末尾
    }

}

//int main()
//{
//    Simplesort mysort;
//    int testA[7] = { 3,16,5,11,8,3,1 };
//
//    cout << "before Sort" << endl;
//    mysort.PrintResult(testA, 7);
//
//    mysort.SelectSort(testA, 7);
//
//    cout << "after Sort" << endl;
//    mysort.PrintResult(testA, 7);
//}


int main()
{
    Simplesort mysort;
    int testA[7] = { 5,16,3,11,8,1,3 };

    cout << "before Sort" << endl;
    mysort.PrintResult(testA, 7);

    mysort.InsertSort(testA,7);

    cout << "after Sort" << endl;
    mysort.PrintResult(testA, 7);
}


//int main()
//{
//    Simplesort mysort;
//    int testA[7] = { 5,16,3,11,8,1,3 };
//
//    cout << "before BubbleSort" << endl;
//    mysort.PrintResult(testA, 7);
//
//    mysort.BubbleSort(testA,7);
//
//    cout << "after BubbleSort" << endl;
//    mysort.PrintResult(testA, 7);
//}
